import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author lzhphantom
 * @description
 * @date 创建于 20:05 2020/8/3
 * @modified
 */
public class Sort {
    /**
     * 冒泡排序
     *
     * @param arr 需要排序的数组
     * @return void
     * @author lzhphantom
     * @date 9:23 2020/8/5
     */
    public static void bubbleSort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) {
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                }
            }
        }
    }

    /**
     * 选择排序
     *
     * @param arr 需要排序的数组
     * @return void
     * @author lzhphantom
     * @date 9:24 2020/8/5
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    minIndex = j;
                    min = arr[j];
                }
            }
            if (i != minIndex) {
                arr[i] = arr[minIndex] ^ arr[i];
                arr[minIndex] = arr[minIndex] ^ arr[i];
                arr[i] = arr[minIndex] ^ arr[i];
            }
        }
    }

    /**
     * 选择排序优化
     *
     * @param arr 需要排序的数组
     * @return void
     * @author lzhphantom
     * @date 9:28 2020/8/5
     */
    public static void goodSelectSort(int[] arr) {
        for (int i = 0; i < arr.length / 2; i++) {
            int minIndex = i;
            int maxIndex = i;
            for (int j = i + 1; j < arr.length - i; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                    continue;
                }
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                    continue;
                }
            }
            if (maxIndex == i && minIndex != arr.length - i - 1) {
                arr[arr.length - i - 1] = arr[maxIndex] ^ arr[arr.length - i - 1];
                arr[maxIndex] = arr[maxIndex] ^ arr[arr.length - i - 1];
                arr[arr.length - i - 1] = arr[maxIndex] ^ arr[arr.length - i - 1];
                arr[i] = arr[minIndex] ^ arr[i];
                arr[minIndex] = arr[minIndex] ^ arr[i];
                arr[i] = arr[minIndex] ^ arr[i];
            } else if (maxIndex == i && minIndex == arr.length - i - i) {
                arr[maxIndex] = arr[minIndex] ^ arr[maxIndex];
                arr[minIndex] = arr[minIndex] ^ arr[maxIndex];
                arr[maxIndex] = arr[minIndex] ^ arr[maxIndex];
            } else {
                arr[i] = arr[minIndex] ^ arr[i];
                arr[minIndex] = arr[minIndex] ^ arr[i];
                arr[i] = arr[minIndex] ^ arr[i];

                arr[maxIndex] = arr[arr.length - i - 1] ^ arr[maxIndex];
                arr[arr.length - i - 1] = arr[arr.length - i - 1] ^ arr[maxIndex];
                arr[maxIndex] = arr[arr.length - i - 1] ^ arr[maxIndex];
            }
        }
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            if (tmp < arr[j]) {
                for (; j >= 0 && tmp < arr[j]; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = tmp;
            }
        }
    }

    /**
     * 希尔排序
     *
     * @param arr 需要排序的数组
     * @return void
     * @author lzhphantom
     * @date 9:29 2020/8/5
     */
    public static void shellSort(int[] arr) {
        // 每次减半，直到步长为 1
        for (int i = arr.length / 2; i > 0; i /= 2) {
            //开始插入排序，每一轮的步长为 i
            for (int j = i; j < arr.length; j += i) {
                for (int k = j - i; k >= 0; k -= i) {
                    // 满足插入那么交换元素
                    if (arr[k + i] < arr[k]) {
                        arr[j] = arr[k + i] ^ arr[j];
                        arr[k + i] = arr[k + i] ^ arr[j];
                        arr[j] = arr[k + i] ^ arr[j];
                        continue;
                    }
                    break;
                }
            }
        }
    }

    /**
     * 归并排序(自顶向下归)
     *
     * @param arr   需要排序的数组
     * @param begin 起始位置
     * @param end   结束位置
     * @return void
     * @author lzhphantom
     * @date 9:29 2020/8/5
     */
    public static void mergeDownSort(int[] arr, int begin, int end) {
        if (end - begin > 1) {
            int mid = begin + (end - begin + 1) / 2;
            mergeDownSort(arr, begin, mid);
            mergeDownSort(arr, mid, end);
            merge(arr, begin, mid, end);
        }
    }

    /**
     * 归并操作
     *
     * @param arr   数组
     * @param begin 起始位置
     * @param mid   中间位置
     * @param end   结束位置（不在数组中）
     * @return void
     * @author lzhphantom
     * @date 9:32 2020/8/5
     */
    private static void merge(int[] arr, int begin, int mid, int end) {
        int leftSize = mid - begin;
        int rightSize = end - mid;
        int newSize = leftSize + rightSize;

        List<Integer> result = new ArrayList<>(newSize);
        int left = 0, right = 0;
        while (left < leftSize && right < rightSize) {
            int leftVal = arr[begin + left];
            int rightVal = arr[mid + right];

            if (leftVal < right) {
                result.add(leftVal);
                left++;
            } else {
                result.add(rightVal);
                right++;
            }
        }
        int[] arr1 = new int[mid - begin - left];
        System.arraycopy(arr, begin + left, arr1, 0, mid - begin - left);
        int[] arr2 = new int[end - mid - right];
        System.arraycopy(arr, mid + right, arr2, 0, end - mid - right);
        result.addAll(Arrays.stream(arr1).boxed().collect(Collectors.toList()));
        result.addAll(Arrays.stream(arr2).boxed().collect(Collectors.toList()));
        int[] resultArr = result.stream().mapToInt(Integer::valueOf).toArray();
        if (newSize >= 0) {
            System.arraycopy(resultArr, 0, arr, begin, newSize);
        }
    }

    /**
     * 归并排序（自底向上）
     *
     * @param arr   数组
     * @param begin 起始位置
     * @param end   结束位置
     * @return void
     * @author lzhphantom
     * @date 9:42 2020/8/5
     */
    public static void mergeUpSort(int[] arr, int begin, int end) {
        int step = 1;
        while ((end - begin) > step) {
            for (int i = begin; i < end; i += step << 1) {
                // 第一数组的下界
                int mid = i + step;
                // 第二数组的上界
                int hi = i + (step << 1);
                if (mid > end) {
                    return;
                }
                if (hi > end) {
                    hi = end;
                }
                merge(arr, i, mid, hi);
            }
            step <<= 1;
        }
    }

    /**
     * 归并操作优化
     *
     * @param arr 数组
     * @param n   数组长度
     * @return void
     * @author lzhphantom
     * @date 9:34 2020/8/5
     */
    public static void goodMergeSort(int[] arr, int n) {
        int blockSize = 3;
        int a = 0, b = blockSize;
        // 按照三个元素为一组进行小数组排序，使用直接插入排序
        while (b <= n) {
            int[] arr1 = new int[b - a];
            System.arraycopy(arr, a, arr1, 0, b - a);
            insertSort(arr1);
            System.arraycopy(arr1, 0, arr, a, b - a);
            a = b;
            b += blockSize;
        }
        if (n - a > 0) {
            int[] arr2 = new int[n - a];
            System.arraycopy(arr, a, arr2, 0, n - a);
            insertSort(arr2);
            System.arraycopy(arr2, 0, arr, a, n - a);
        }

        // 将这些小数组进行归并
        while (blockSize < n) {
            a = 0;
            b = 2 * blockSize;
            for (; b <= n; b += 2 * blockSize) {
                goodMerge(arr, a, a + blockSize, b);
                a = b;
            }
            int m = a + blockSize;
            if (m < n) {
                goodMerge(arr, a, m, n);
            }
            blockSize *= 2;
        }
    }

    /**
     * 原数组归并
     *
     * @param arr   数组
     * @param begin 起始位置
     * @param mid   中间位置
     * @param end   结束位置（不在数组中）
     * @return void
     * @author lzhphantom
     * @date 10:14 2020/8/5
     */
    private static void goodMerge(int[] arr, int begin, int mid, int end) {
        int i = begin, j = mid, k = end - 1;
        while (j - 1 > 0 && k - j >= 0) {
            int step = 0;
            // 从 i 向右移动，找到第一个 array[i]>array[j]的索引
            while (j - i > 0 && arr[i] <= arr[j]) {
                i++;
            }
            // 从 j 向右移动，找到第一个 array[j]>array[i]的索引
            while (k - j >= 0 && arr[j] <= arr[i]) {
                j++;
                step++;
            }
            rotation(arr, i, j - step, j - 1);
            i += step;
        }
    }

    /**
     * 手摇算法
     *
     * @param arr   数组
     * @param left  起始位置
     * @param mid   中间位置
     * @param right 结束位置
     * @return void
     * @author lzhphantom
     * @date 10:17 2020/8/5
     */
    private static void rotation(int[] arr, int left, int mid, int right) {
        reverse(arr, left, mid - 1);
        reverse(arr, mid, right);
        reverse(arr, left, right);
    }

    /**
     * 数组逆序
     *
     * @param arr   数组
     * @param left  起始
     * @param right 结束
     * @return void
     * @author lzhphantom
     * @date 10:18 2020/8/5
     */
    private static void reverse(int[] arr, int left, int right) {
        while (left < right) {
            arr[left] = arr[right] ^ arr[left];
            arr[right] = arr[right] ^ arr[left];
            arr[left] = arr[right] ^ arr[left];
            left++;
            right--;
        }
    }

    /**
     * 普通堆排序
     *
     * @param arr 数组
     * @return void
     * @author lzhphantom
     * @date 10:12 2020/8/6
     */
    public static void heapSort(int[] arr) {
        Heap heap = new Heap(arr);
        for (int i : arr) {
            heap.push(i);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            arr[i] = heap.pop();
        }
    }

    /**
     * 先自底向上构建最大堆，再移除堆元素实现堆排序
     *
     * @param arr 数组
     * @return void
     * @author lzhphantom
     * @date 10:12 2020/8/6
     */
    public static void heapUpSort(int[] arr) {
        int count = arr.length;
        // 最底层的叶子节点下标，该节点位置不定，但是该叶子节点右边的节点都是叶子节点
        int start = count / 2 + 1;
        // 最后的元素下标
        int end = count - 1;

        // 从最底层开始，逐一对节点进行下沉
        while (start >= 0) {
            sift(arr, start, count);
            // 表示左偏移一个节点，如果该层没有节点了，那么表示到了上一层的最右边
            start--;
        }
        // 下沉结束了，现在要来排序了
        // 元素大于2个的最大堆才可以移除
        while (end > 0) {
            // 将堆顶元素与堆尾元素互换，表示移除最大堆元素
            arr[end] = arr[0] ^ arr[end];
            arr[0] = arr[0] ^ arr[end];
            arr[end] = arr[0] ^ arr[end];
            // 对堆顶进行下沉操作
            sift(arr, 0, end);
            // 一直移除堆顶元素
            end--;
        }
    }

    /**
     * 元素下沉
     *
     * @param arr   数组
     * @param start 下沉元素下标
     * @param count 用来判断是否到底堆底，使得下沉结束
     * @return void
     * @author lzhphantom
     * @date 10:18 2020/8/6
     */
    private static void sift(int[] arr, int start, int count) {
        int root = start;
        int child = root * 2 + 1;

        while (child < count) {
            if (count - child > 1 && arr[child] < arr[child + 1]) {
                child++;
            }
            if (arr[root] < arr[child]) {
                arr[root] = arr[child] ^ arr[root];
                arr[child] = arr[child] ^ arr[root];
                arr[root] = arr[child] ^ arr[root];

                root = child;
                child = 2 * root + 1;
            } else {
                return;
            }
        }
    }

    /**
     * 快速排序
     *
     * @param arr   数组
     * @param start 开始下标
     * @param end   结束下标
     * @return void
     * @author lzhphantom
     * @date 15:53 2020/8/10
     */
    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int loc = partition(arr, start, end);
            quickSort(arr, start, loc - 1);
            quickSort(arr, loc + 1, end);
        }
    }

    /**
     * 切分函数
     *
     * @param arr   数组
     * @param begin 起始下标
     * @param end   结束下标
     * @return int 切分元素的下标
     * @author lzhphantom
     * @date 15:40 2020/8/10
     */
    private static int partition(int[] arr, int begin, int end) {
        // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较
        int i = begin + 1;
        // array[end]是数组的最后一位
        int j = end;

        while (i < j) {
            if (arr[i] > arr[begin]) {
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                j--;
            } else {
                i++;
            }
        }
        if (arr[i] >= arr[begin]) {
            i--;
        }
        if (i != begin) {
            arr[begin] = arr[i] ^ arr[begin];
            arr[i] = arr[i] ^ arr[begin];
            arr[begin] = arr[i] ^ arr[begin];
        }

        return i;
    }

    /**
     * 快速排序优化1
     * 小规模数组的情况下，直接插入排序的效率最好
     *
     * @param arr   数组
     * @param start 起始下标
     * @param end   结束下标
     * @return void
     * @author lzhphantom
     * @date 16:35 2020/8/10
     */
    public static void goodQuickSort1(int[] arr, int start, int end) {
        if (start < end) {
            //优化1
            // 当数组小于 4 时使用直接插入排序
            if (end - start <= 4) {
                int[] arr1 = new int[end - start];
                System.arraycopy(arr, start, arr1, 0, end - start);
                insertSort(arr1);
                System.arraycopy(arr1, 0, arr, start, end - start);
                return;
            }
            int loc = partition(arr, start, end);
            goodQuickSort1(arr, start, loc - 1);
            goodQuickSort1(arr, loc + 1, end);
        }
    }

    /**
     * 伪尾递归快速排序
     *
     * @param arr   数组
     * @param start 起始下标
     * @param end   结束下标
     * @return void
     * @author lzhphantom
     * @date 16:38 2020/8/10
     */
    public static void goodQuickSort3(int[] arr, int start, int end) {
        while (start < end) {
            if (end - start <= 4) {
                int[] arr1 = new int[end - start];
                System.arraycopy(arr, start, arr1, 0, end - start);
                insertSort(arr1);
                System.arraycopy(arr1, 0, arr, start, end - start);
                return;
            }
            int loc = partition(arr, start, end);
            if (loc - start < end - loc) {
                goodQuickSort3(arr, start, loc - 1);
                start = loc + 1;
            } else {
                goodQuickSort3(arr, loc + 1, end);
                end = loc - 1;
            }
        }
    }

    /**
     * 三切分的快速排序
     * 排序数列可能存在大量重复值，使用三向切分快速排序，将数组分成三部分，大于基准数，等于基准数，小于基准数，这个时候需要维护三个下标。
     *
     * @param arr   数组
     * @param start 起始下标
     * @param end   结束下标
     * @return void
     * @author lzhphantom
     * @date 16:39 2020/8/10
     */
    public static void goodQuickSort2(int[] arr, int start, int end) {
        if (start < end) {

            int[] loc = partition3(arr, start, end);
            goodQuickSort2(arr, start, loc[0] - 1);
            goodQuickSort2(arr, loc[1] + 1, end);
        }
    }

    /**
     * 切分函数
     *
     * @param arr   数组
     * @param begin 起始下标
     * @param end   结束下标
     * @return int[] 返回切分元素的下标
     * @author lzhphantom
     * @date 16:40 2020/8/10
     */
    private static int[] partition3(int[] arr, int begin, int end) {
        int left = begin;
        int right = end;
        int mid = begin + 1;
        int base = arr[begin];

        while (mid <= right) {
            if (arr[mid] > base) {
                if (mid != right) {
                    arr[mid] = arr[right] ^ arr[mid];
                    arr[right] = arr[right] ^ arr[mid];
                    arr[mid] = arr[right] ^ arr[mid];
                }
                right--;
            } else if (arr[mid] < base) {
                if (mid != left) {
                    arr[mid] = arr[left] ^ arr[mid];
                    arr[left] = arr[left] ^ arr[mid];
                    arr[mid] = arr[left] ^ arr[mid];
                }
                left++;
                mid++;
            } else {
                mid++;
            }
        }
        return new int[]{left, right};
    }

}
